Tanya Khovanova's Math Blog

Here is a baby puzzle. On Monday the baby said A, on Tuesday AU, on Wednesday AUUA, on Thursday AUUAUAAU. What will she say on Saturday?

You can see that this very gifted baby increases her talking capacity twice each day. The first half of what she says repeats her speech of the day before; and the second half is like the first half, but switches every A and U. If the baby continues indefinitely, her text converges to an infinite sequence that mathematicians call the Thue-Morse sequence (A010060). Of course, mathematicians use zeroes and ones instead of A and U, so the sequence looks like 0110100110010110100….

This sequence has many interesting properties. For example, if you replace every zero by 01 and every one by 10 in the Thue-Morse sequence, you will get the Thue-Morse sequence back. You can see that this is so if you code A in the baby’s speech by 01 and U by 10. Thus the Thue-Morse sequence is a fixed point under this substitution. Moreover, the only two fixed points under this substitution are the Thue-Morse sequence and its negation (A010059).

The Thue-Morse sequence possesses many other cool properties. For example, the sequence doesn’t contain substrings 000 and 111. Actually any sequence built from the doubles 01 and 10 can’t contain the triples 000 and 111 because we switch the digit after every odd-indexed term of such a sequence. A more general and less trivial statement is also true for the Thue-Morse sequence: it doesn’t contain any cubes. That is, it doesn’t contain XXX, where X is any binary string.

I stumbled upon this sequence when I was playing with evil and odious numbers invented by John H. Conway. A number is evil if the number of ones in its binary expansion is even, and odious if it’s odd. We can define a function, called the odiousness of a number, in the following way: odiousness(n) is one, if n is odious and 0 otherwise. We can apply the odiousness function to a sequence of non-negative integers term-wise. Now I can describe the Thue-Morse sequence as the odiousness of the sequence of non-negative numbers. Indeed, the odiousness of the number 2ⁿ + k is opposite of the odiousness of k, if k is less than 2ⁿ. That means if we already know the odiousness of the numbers below 2ⁿ, the next 2ⁿ terms of the odiousness sequence is the bitwise negation of the first 2ⁿ terms. So odiousness is built the same way as the Thue-Morse sequence, and you can easily check that the initial terms are the same too.

Let me consider as an example the sequence which is the odiousness of triangular numbers A153638: 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0…. What can we say about this sequence? We can say that the number of zeroes is infinite, as all the terms with indices of the form 2^n-1(2ⁿ+1) are zeroes. Also, the number of ones is infinite because all the terms with indices of the form 2^2n-1(2^2n-1-1) are ones.

Obviously, we can define the evilness of a number or of a sequence with non-negative terms. Namely, the evilness of a number is 1 if the number is evil, and 0 if it is not. The evilness is the bitwise negation of the odiousness. The evilness of the sequence of non-negative integers is the negation of the Thue-Morse sequence. The odiousness sequence of any sequence of zeroes and ones is the sequence itself, and the evilness sequence is its negation.

I would like to define an inverse odiousness operation on binary sequences. Many different sequences can have the same odiousness sequence. In such a case mathematicians usually define the inverse operation as a minimal non-negative sequence whose odiousness is the given sequence. Obviously, the minimal inverse of a binary sequence is the sequence itself, and thus not very interesting. I suggest that we define the inverse as a minimal increasing sequence. In this case the odiousness inverse of the Thue-Morse sequence is the sequence of non-negative numbers.

For example, let me describe the inverse odiousness of the sequence of all ones. Naturally, all the numbers in the sequence must be odious, and by minimality property this is the sequence of odious numbers A000069: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19…. Analogously, the odiousness inverse of the sequence of all zeroes is the sequence of evil numbers A001969: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20….

Let us find the odiousness inverse of the alternating sequence A000035: 0, 1, 0, 1, 0, 1…. This is the lexicographically smallest sequence of numbers changing putridity. By the way, “putridity” is the term suggested by John Conway to encompass odiousness and evilness the same way as parity encompasses oddness and evenness.

The odiousness inverse of the alternating sequence is the sequence A003159: 0, 1, 3, 4, 5, 7, 9, 11, 12, 13…. By my definition we can describe this sequence as indices of terms of the Thue-Morse sequence that are different from the previous term. This sequence can be described in many other ways. For example, the official definition in the OEIS is that this sequence consists of numbers whose binary expansion ends with an even number of zeroes. It is fun to prove that this is the case. It is also fun to show that this sequence can be built by adding numbers to it that are not doubles of previous terms.

Let us look at the first differences of the previous sequence. This is the sequence A026465: 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2… — the length of n-th run of identical symbols in the Thue-Morse sequence. As we know that the Thue-Morse sequence doesn’t contain three ones or three zeroes in a row, we can state that the terms of this sequence will continue to be ones or twos.

You can define putridity sequences for any non-negative sequence. Which of them are interesting? I do not know, but I know which of them are not very interesting. For example, the putridity of pronic (oblong) numbers sequence is the same as the putridity of the triangular numbers sequence. This is because pronic numbers are twice triangular numbers and putridity is independent of factors of two. Another uninformative putridity sequence is the odiousness of the powers of two. This sequence consists only of ones.

I bet that my readers can find putridity sequences that are interesting.